package realQuestion.didi.xuanzhanArr;

//TODO:2023/12/30  搜索旋转数组
public class Class10_03 {
    public int search(int[] arr, int target) {
        int left = 0;
        int right = arr.length-1;

        while (left <= right) {
//          有效防止了left和right太大直接相加导致溢出。
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                if(arr[0] == arr[mid]){ return 0; }
                while (mid > 1 && arr[mid - 1] == arr[mid]) {
                    mid--;
                }
                return mid;
            } else if (arr[mid] > arr[left]) {
                //TODO:2023/12/30   这种情况下中间位置左侧一定是递增的 也不一定
                if (arr[left] <= target && target < arr[mid]) {
                    //TODO:2023/12/30 target的值在左侧区间
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else if (arr[mid] < arr[left]) {
                //TODO:2023/12/30     这种情况下中间位置左侧并非完全单调递增的
                if (arr[mid] < target && target <= arr[right]) {
                    //TODO:2023/12/30 target的值在右侧
                    left = mid + 1;
                } else  {
                    right = mid - 1;
                }
            } else if (arr[mid]==arr[left]) {
                left++;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Class10_03 class10_03 = new Class10_03();
        int[] arr={15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14};
        System.out.println(class10_03.search(arr, 11));

    }

}
